﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//题:
//给定一个长度为 n 的整型数组 arr 和一个整数 k(k > 1) 。
//已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。
//请返回只出现了 1 次的数。
//数据范围 : 1 \le n \le 2 * 10 ^ 51≤n≤2∗10
//进阶：时间复杂度 O(32n)O(32n)，空间复杂度 O(1)O(1)


//思路:
//数组内除了目标元素外，其余元素个数都是k个
//那么其余元素对应位的二进制数之和，要么是0，要么是k的整数倍
//如:00000000 00000000 00000000 00000101  数组内的元素 '5' 的二进制数
//   00000000 00000000 00000000 00000101
//   00000000 00000000 00000000 00000101 
//   00000000 00000000 00000000 00000303  二进制数对应位之和，要么是0，要么是k的倍数   其他元素亦是如此    所有其余元素二进制数对应位之和 也满足这个规律 
int fdN(int* arr, int n, int k)
{
    // write code here
    int result = 0;
    for (int i = 0; i < 32; i++)
    {
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (arr[j] & (1 << i))
            {
                count++;//count是arr数组内所有元素的二进制数对应位之和   由于除目标元素外的所有元素的个数都是k  
            }
        }
        if (count % k == 1)//此时目标元素的二进制数，从右向左移第i位  必为1
            //^ 同为0  异为1
            result ^= (1 << i);//此过程相当于把目标元素二进制数中的1补全到0的二进制数对应位上
        //00000000 00000000 00000000 00000000  为1的对应位全换成1
    }
    return result;
}

int main()
{
	int arr[] = { 5,4,1,1,5,1,5 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    int ret=fdN(arr, sz, k);
    printf("%d\n", ret);
	return 0;
}